# -*- coding: utf-8 -*-

"""240. 搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例 1：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

示例 2：
输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

提示：
m == matrix.length
n == matrix[i].length
1 <= n, m <= 300
-10^9 <= matrix[i][j] <= 10^9
每行的所有元素从左到右升序排列
每列的所有元素从上到下升序排列
-10^9 <= target <= 10^9"""

class Solution:
    """从左上角看到一个杨辉三角，准备分层用二分查找的方式查询，发现有bug，遂放弃。
    换个角度，从右上角为顶点看，就是一个查找杨辉三角（类似查找二叉树，只不过不是树结构，是杨辉三角结构），那么高效查询方式豁然开朗"""
    def searchMatrix(self, matrix, target: int) -> bool:
        row, col = 0, len(matrix[0])-1
        while True:
            try:
                num = matrix[row][col]
            except IndexError:
                return False

            if num == target:
                return True
            if target > num:
                row += 1
            else:
                col -= 1


if __name__ == '__main__':
    so = Solution()
    print(so.searchMatrix(matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5))
    print(so.searchMatrix(matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20))
    # so.searchMatrix()
    # so.searchMatrix()


